import fun.ipconfig.avl.AvlTreeNode;
import fun.ipconfig.avl.DataStorage;
import fun.ipconfig.rb.RbTree;
import fun.ipconfig.rb.RbTreeStorage;
import fun.ipconfig.rb.RbTreeNode;
import fun.ipconfig.sort.QuickSort;

import java.util.*;

/**
 * 测试用例
 * @author gtinlian
 */
public class App {
    public static AvlTreeNode<DataStorage> add(AvlTreeNode<DataStorage> node, int index, int max){
        for(int i = index;i<max;i++){
            node = node.insert(new DataStorage(i));
        }
        return node;
    }
    public static void avlTest() {

        // 调整测试量
        int check = 20;
        // 进行取余删除
        int delRemainder = 3;
        //初始化树节点
        AvlTreeNode<DataStorage> node = new AvlTreeNode<DataStorage>(new DataStorage(1));
        Long start = System.currentTimeMillis();
        // 批量添加数据
        node = add(node,2,check);
        long addTime = (System.currentTimeMillis() - start);
        
        for(int i = 0;i<check;i++){
            if(i%delRemainder==0){
                System.out.println("  已经删除 i:"+i+",    ");
                node = node.delete(new DataStorage(i));
            }
            if(i%(delRemainder)==0){
                node = node.insert(new DataStorage(i/2));
            }
            AvlTreeNode<DataStorage> swap = node.find(new DataStorage(i));
            System.out.println(swap != null ?  "( 已经找到 i: "+swap.getData().index() +" )": "  无法查找到 i: "+ i);
        }

        System.out.println("插入耗时: "+addTime +"ms");
        System.out.println(node);
    }
    public static void rbTreeTest(){
        /**初始化测试对象*/
        AvlTreeNode<DataStorage> node = new AvlTreeNode<DataStorage>(new DataStorage(10));
        RbTree<RbTreeStorage> rb = new RbTree<RbTreeStorage>();
        rb.insert(new RbTreeNode<>(new RbTreeStorage(10L)));
        Map<Long,Long> m= new HashMap<Long,Long>(10);
        
        /**生成测试数据*/
        int insertNumber = 1000000;
        List<Long> lis = new ArrayList<>(insertNumber);
        for(int i=0;i<insertNumber;i++){
            long data = new Random().nextLong();
            lis.add(data);
        }
        
        /** 红黑树插入测试 */
        System.out.println("add ok: 测试插入数据: " + insertNumber);
        long s = System.currentTimeMillis();
        lis.forEach(f->{
            rb.insert(new RbTreeNode<>(new RbTreeStorage(f)));
        });
        
        /** 平衡二叉树插入测试 */
        System.out.println("红黑树插入耗时: "+ (System.currentTimeMillis() - s));
        long avl = System.currentTimeMillis();
        for(Long f : lis){
            node = node.insert(new DataStorage(f));
        }
        System.out.println("平衡二叉树插入耗时: "+ (System.currentTimeMillis() - avl));

        /** HashMap插入测试 */
        long h = System.currentTimeMillis();
        lis.forEach(f->{
            m.put(f,f);
        });
        System.out.println("HashMap插入耗时: "+ (System.currentTimeMillis() - h));
        
        /**数据查找测试*/
        int findindex = 10000;
        for(int i = 0;i<findindex;i++){
            System.out.println("红黑树查找: "+rb.find(new RbTreeNode<>(new RbTreeStorage(lis.get(i)))).getData().index());
        }
        for(int i = 0;i<findindex;i++){
            System.out.println("平衡二叉树查找耗时"+node.find(new DataStorage(lis.get(i))).getData().index());
        }
    }

    public static void quickSort(){
        int index = 10000;
        int arr[] = new int[index];
        for(int i = index-1;i>=0;i--){
            arr[i] = i;
        }
        QuickSort.sort(arr);
        for(int i : arr){
            System.out.println(i);
        }
    }

    public static void main(String[] args) {
//        rbTreeTest();
//        quickSort();
        avlTest();
    }
}


